#include "Node.h"
#include "defs.h"

#include <deque>
#include <iostream>

namespace jcrada {

    Node::Node( int arity ) :
    _parent( NULL ),
    _arity( arity ),
    _children( NULL ) {
        if (getArity() > 0) {
            _children = new Node*[getArity()];
            for (int i = 0; i < getArity(); ++i) {
                setChild(NULL, i);
                //                _children[i] = NULL;
            }
        }
    }

    Node::~Node( ) {
        remove();
        for (int i = 0; i < getArity(); ++i) {
            if (getChild(i) != NULL) {
                delete getChild(i);
            }
        }
        delete [] _children;
    }

    void Node::moveTo( Node* parent, int position ) {
        remove();
        setParent(parent);
        if (parent != NULL) {
            if (position == -1) {
                for (int i = 0; i < parent->getArity(); ++i) {
                    if (parent->getChild(i) == NULL) {
                        position = i;
                    }
                }
                assert(position > -1);
            }
            assert(parent->getArity() > 0 && parent->_children[position] == NULL);
            parent->setChild(this, position);
        }
    }

    void Node::remove( ) {
        if (getParent() != NULL) {
            getParent()->removeChild(this);
        }
    }

    void Node::removeChild( Node* child ) {
        for (int i = 0; i < getArity(); ++i) {
            if (getChild(i) == child) {
                setChild(NULL, i);
                break;
            }
        }
        child->setParent(NULL);
    }

    Node* Node::findNodeInSubtreeUsingBFS( int position ) {
        if (position == 0) {
            return this;
        }
        //BFS
        const Node* n = NULL;
        std::deque<const Node*> deque;
        deque.push_back(this);
        int counter = 0;
        while (deque.size() > 0) {
            n = deque.front();
            for (int i = 0; i < n->getArity(); ++i) {
                if (++counter == position) {
                    return n->getChild(i);
                }
                deque.push_back(n->getChild(i));
            }
            deque.pop_front();
        }
        return NULL;
    }

    int Node::findPositionInSubtreeUsingBFS( const Node* node ) const {
        if (this == node) {
            return 0;
        }
        //BFS
        int result = 0;
        std::deque<const Node*> deque;
        deque.push_back(node);
        while (deque.size() > 0) {
            node = deque.front();
            for (int i = 0; i < node->getArity(); ++i) {
                ++result;
                if (node->getChild(i) == node) {
                    return result;
                }
                deque.push_back(node->getChild(i));
            }
            deque.pop_front();
        }
        return result;
    }

    int Node::getTreeSize( ) const {
        int result = 1;
        //BFS
        const Node* n = NULL;
        const Node* child = NULL;
        std::deque<const Node*> deque;
        deque.push_back(this);
        while (deque.size() > 0) {
            n = deque.front();
            for (int i = 0; i < n->getArity(); ++i) {
                child = n->getChild(i);
                if (child != NULL) {
                    deque.push_back(child);
                    ++result;
                }
            }
            deque.pop_front();
        }
        return result;
    }

    Node* Node::clone( ) const {
        Node* result = new Node(getArity());
        Node* child = NULL;
        for (int i = 0; i < getArity(); ++i) {
            if (getChild(i) != NULL) {
                child = getChild(i)->clone();
                child->moveTo(result, i);
            }
        }
        return result;
    }

    std::string Node::toString( ) const {
        return "Node[*=" + TO_STRING(reinterpret_cast<int> (this)) + "]";
    }

    std::string Node::toStringDown( int level) const {
        std::string result;
        result += "Node[p=" + (getParent() ? getParent()->toString() : "NULL") +
                ";a=" + TO_STRING(getArity()) + "; n={";
        for (int i = 0; i < getArity(); ++i) {
            if (getChild(i) != NULL) {
                result += getChild(i)->toStringDown() + ";";
            }
        }
        result += " } ]";
        return result;
    }

    std::string Node::toStringUp( ) const {
        std::string result;
        const Node * n = getParent();
        int depth = 0;
        if (n != NULL) {
            result = n->toStringUp();
        }
        result += toString() + "->";

        if (depth >= 1000) {
            BDEBUG("WARN: Circular Tree or tree depth > 1000");
        }
        return result;
    }

    int Node::getDepth( const Node* node ) {
        //DFS
        if (node == NULL) {
            return 0;
        }
        int max = 0;
        for (int i = 0; i < node->getArity(); ++i) {
            int tmp_depth = 0;
            if (node->getChild(i) != NULL) {
                tmp_depth = getDepth(node->getChild(i));
                ++tmp_depth;
            }
            if (tmp_depth > max) {
                max = tmp_depth;
            }
        }
        return max;
    }

    Node* Node::getRoot() {
        Node* root = this;
        while(root->getParent() != NULL){
            root = root->getParent();
        }
        return root;
    }

    void Node::toXml(QDomDocument& xml, QDomElement* parent ) const {
        QDomElement node = xml.createElement("Node");
        node.setAttribute("arity",getArity());
        Node* child = NULL;
        for (int i = 0 ; i < getArity() ;++i){
            child = getChild(i);
            if (child){
                child->toXml(xml,&node);
            }
        }
        if (parent){
            parent->appendChild(node);
        }else{
            xml.appendChild(node);
        }
    }

    std::string Node::toXml() const{
        QDomDocument doc;
        this->toXml(doc);
        return doc.toString().toStdString();
    }

    int Node::main( int argc, char** argv ) {
        Node* node = new Node(3);
        Node* l1a = new Node(2);
        Node* l2a = new Node(1);
        Node* l3a = new Node(0);
        Node* l1b = new Node(1);
        Node* l2b = new Node(1);
        DEBUGM;
        l3a->moveTo(l2a, 0);
        DEBUGM;
        l2a->moveTo(l1a, 0);
        DEBUGM;
        l1a->moveTo(node, 0);
        DEBUGM;
        l2b->moveTo(l1b, 0);
        DEBUGM;
        l1b->moveTo(node, 1);
        DEBUGM;

        std::cout << "root=" << node->toString() << std::endl;
        std::cout << "down" << std::endl;
        std::cout << node->toStringDown() << std::endl;
        std::cout << "up" << std::endl;
        std::cout << l3a->toStringUp() << std::endl;
        std::cout << "test" << std::endl;
        std::cout << node->toStringUp() << std::endl;

        return 0;
    }

}
